package com.cloud.freeflow.common.utils;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.collections.CollectionUtils;

import com.cloud.freeflow.common.result.QkTreeNode;


/**
 * 树算法工具类
 * 
 * @author taominglong
 *
 */
public class TreeHelper {

	/**
	 * 递归将List封装为树节点
	 * 
	 * @param elements
	 * @return
	 */
	public static final QkTreeNode[] buildList2Tree(List<QkTreeNode> elements) {
		List<QkTreeNode> roots = new ArrayList<QkTreeNode>();
		for (QkTreeNode node : elements) {
			if (node.isRootFlag()) {
				roots.add(node);
			}
		}
		@SuppressWarnings("unchecked")
		List<QkTreeNode> notRoots = (List<QkTreeNode>) CollectionUtils.subtract(elements, roots);
		for (QkTreeNode root : roots) {
			root.setChildren(findChildren(root, notRoots));
		}
		return roots.toArray(new QkTreeNode[roots.size()]);
	}

	
	private static List<QkTreeNode> findChildren(QkTreeNode root, List<QkTreeNode> allNodes) {
		List<QkTreeNode> children = new ArrayList<QkTreeNode>();
		for (QkTreeNode node : allNodes) {
			if (node.getSeniorId().equals(root.getId())) {
				node.setLevel(root.getLevel() + 1);
				children.add(node);
			}
		}
		@SuppressWarnings("unchecked")
		List<QkTreeNode> notChildren = (List<QkTreeNode>) CollectionUtils.subtract(allNodes, children);
		for (QkTreeNode child : children) {
			List<QkTreeNode> c = findChildren(child, notChildren);
			if (c.size() < 1) {
				child.setLeaf(true);
			} else {
				child.setLeaf(false);
			}
			child.setChildren(c);
		}
		return children;
	}
}
